public class Offer19 {
    public boolean isMatch(String s, String p) {
        if(s==null||p==null){
            return false;
        }
        char[] schars = s.toCharArray();
        char[] pchars = p.toCharArray();
        return matchChar(schars,pchars,0,0);
    }
    public boolean matchChar(char[] schars,char[] pchars,int sstart,int pstart){
        if (sstart>=schars.length&&pstart>=pchars.length){
            return true;
        }
        if (sstart!=schars.length&&pstart==pchars.length){
            return false;
        }
        if (pstart+1<pchars.length&&pchars[pstart+1]=='*'){
            if ((sstart<schars.length&&pchars[pstart]==schars[sstart])
                    || pchars[pstart]=='.'&&sstart<schars.length){
                return matchChar(schars, pchars, sstart, pstart+2) ||
                        matchChar(schars, pchars, sstart+1, pstart+2) ||
                        matchChar(schars, pchars, sstart+1, pstart);
            }else {
                return matchChar(schars, pchars, sstart, pstart+2);
            }
        }
        if (sstart<schars.length&&schars[sstart]==pchars[pstart]||pchars[pstart]=='.'&&sstart<schars.length){
            return matchChar(schars, pchars, sstart+1, pstart+1);
        }
        return false;

    }

    public static void main(String[] args) {
        Offer19 offer19 = new Offer19();
        System.out.println(offer19.isMatch("a", ".*..a*"));
    }
}
